#include<iostream>
#include<vector>
using namespace std;

// 打印数组
void disp(vector<int>&R)
{
	for (int i=0; i<R.size(); i++)
		printf("%d ",R[i]);
	printf("\n");
}

// 将R[low..mid]和R[mid+1..high]两个相邻的有序子序列归并为有序子序列R[low..high]
void Merge(vector<int>&R,int low,int mid,int high)
{
	// 辅助数组
	vector<int> R1;
	
	// i、j分别为两个子表的下标
	int i=low, j=mid+1;
	
	// 在子表1和子表2均未遍历完时循环
	while (i<=mid && j<=high)
		if (R[i] <= R[j]) // 将子表1中的元素归并到R1
		{
			R1.push_back(R[i]);
			i++; 
		}
		else // 将子表2中的元素归并到R1
		{
			R1.push_back(R[j]);
			j++; 
		}
	
	// 将子表1余下元素归并到R1
	while (i <= mid)
	{
		R1.push_back(R[i]);
		i++; 
	}
	
	// 将子表2余下元素归并到R1
	while (j <= high)
	{
		R1.push_back(R[j]);
		j++;;
	}
	
	// 将R1复制回R中
	for (int k=0, i=low; i<=high; k++, i++)
		R[i] = R1[k];
}

// 自底向上的二路归并排序算法
void MergePass(vector<int>&R, int length)
{
	// 获取数组大小
	int i, n=R.size();
	
	// 归并length长的两相邻子表
	for (i=0; i+2*length-1<n; i=i+2*length)
		Merge(R, i, i+length-1, i+2*length-1);
	
	// 余下两个子表,后者长度小于length
	if (i+length-1 < n)
		Merge(R,i,i+length-1,n-1); // 归并这两个子表
}

// 自底向上的二路归并算法
void MergeSort1(vector<int> &R)
{
	for (int length=1;length<R.size();length=2*length)
		MergePass(R, length);
}

// 自顶向下的二路归并排序算法
void MergeSort21(vector<int>&R,int low,int high)	
{
	// 子序列有两个或以上元素
	if (low < high)
	{
		// 取中间位置
		int mid = (low+high)/2;
		
		// 对a[low..mid]子序列排序
		MergeSort21(R, low, mid);
		
		// 对a[mid+1..high]子序列排序
		MergeSort21(R, mid+1, high);	
		
		// 将两子序列合并
		Merge(R, low, mid, high);
	}
}

// 二路归并算法
void MergeSort2(vector<int>&R)
{
	// 数组长度
	int n = R.size();
	MergeSort21(R, 0, n-1);
}


int main()
{
	// 创建数组
	vector<int> a={2, 5, 1, 7, 10, 6, 9, 4, 3, 8};
	
	// 打印数组
	printf("排序前:"); disp(a);
	
	// 归并排序
	MergeSort2(a);
	
	// 打印
	printf("排序后:"); disp(a);
	return 0;
}

